package net.lainiao.leetcode;


import net.lainiao.leetcode.base.Common;
import net.lainiao.leetcode.base.TreeNode;

public class LintCode73 {
    //根据中序遍历和后序遍历树构造二叉树
    public static void main(String[] args) {
        int[] mds = {1,2,3};
        int[] bds = {2,1,3};
        LintCode73 code = new LintCode73();
        TreeNode root = code.buildTree(mds, bds);
        Common.showJsonForObject(root,true);
    }

    private int inIndex;
    private int beIndex;
    public TreeNode buildTree(int[] inOrder, int[] beOrder) {
      inIndex=0;
      beIndex=0;
      return buildTreeNode(inOrder,beOrder,null);
    }

    private TreeNode buildTreeNode(int[] inOrder, int[] beOrder, TreeNode endNode) {
        if(beIndex>=beOrder.length){
            return null;
        }
        TreeNode current=new TreeNode(beOrder[beIndex]);
        beIndex++;
        if(current.val!=inOrder[inIndex]){
            current.left=buildTreeNode(inOrder,beOrder,current);
        }
        inIndex++;
        if(endNode==null||endNode.val!=inOrder[inIndex]){
            current.right=buildTreeNode(inOrder,beOrder,endNode);
        }
        return current;
    }


}
